class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        begin = 1
        end = len(nums)-1
        n = end+1-begin
        shouldCount = 0
        if n%2==0:
            shouldCount=n//2
        else:
            shouldCount=(n-1)//2
        while begin<end:
            mid = (begin+end)//2
            count=0
            for num in nums:
                if num > mid:
                    count+=1
            if count<=shouldCount:
                end=mid
                n = end+1-begin
                if n%2==0:
                    shouldCount+=n//2
                else:
                    shouldCount+=(n-1)//2
            else:
                begin=mid+1
                n = end+1-begin
                if n%2==0:
                    shouldCount-=(n-n//2)
                else:
                    shouldCount-=(n-(n-1)//2)
        return begin

print(Solution().findDuplicate([1,1,2]))